3936. Ханойские башни

Даны три стержня. На первом стержне находится несколько дисков сверху вниз по возрастанию размера диска. Два другие пустые. Требуется перенести все диски с первого стержня на второй. Переносить диски разрешается только по одному. Не разрешается класть больший диск на меньший.

Вход. Количество дисков n (1 ≤ n ≤ 19) на первом стержне.

Выход.  Выведите по два числа в строке – номера стержней, откуда и куда переносится диск. Решение должно быть кратчайшим.

Пример входа	Пример выхода
3	1 2 1 3 2 3 1 2 3 1 3 2 1 2

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Пусть требуется перенести n дисков со стержня А на стержень B при помощи стержня C.

Воспользуемся следующей рекурсивной схемой:

· перенесем n – 1 дисков со стержня А на стержень C, используя B;

· перенесем диск со стержня А на стержень B;

· перенесем n – 1 дисков со стержня C на стержень B, используя А;

Реализация алгоритма

Функция hanoi моделирует перенос дисков со стержня from на стержень to, используя дополнительный стержень additional.

void hanoi(int n, int from, int to, int additional)

{

if (n == 0) return;

hanoi(n-1,from,additional,to);

printf("%d %d\n",from,to);

hanoi(n-1,additional,to,from);

}

Читаем количество дисков n. Моделируем работу ханойских башен по переносу n дисков с первого стержня на второй, используя третий.

scanf("%d",&n);

hanoi(n,1,2,3);

Java реализация

import java.util.*;

public class Main

{

static void hanoi(int n, int from, int to, int additional)

{

if (n == 0) return;

hanoi(n-1,from,additional,to);

System.out.println(from + " " + to);

hanoi(n-1,additional,to,from);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

hanoi(n,1,2,3);

con.close();

}

}

Python реализация

def hanoi(n, fro, to, additional) :

if (n == 0) : return

hanoi(n-1,fro,additional,to)

print(fro,to)

hanoi(n-1,additional,to,fro)

n = int(input())

hanoi(n,1,2,3)